package forth

/*
	给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。

	单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
	同一个单元格内的字母不允许被重复使用。

	例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。


	示例 1：

	输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
	输出：true
	示例 2：

	输入：board = [["a","b"],["c","d"]], word = "abcd"
	输出：false

	提示：

	1 <= board.length <= 200
	1 <= board[i].length <= 200
	board 和 word 仅由大小写英文字母组成

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func Exist(board [][]byte, word string) bool {
	return exist(board, word)
}

func exist(board [][]byte, word string) bool {
	if "" == word {
		return false
	}
	m := make([][]bool, len(board))
	for i := 0; i < len(board); i++ {
		m[i] = make([]bool, len(board[i]))
	}
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if _exist(board, word, i, j, m) {
				return true
			}
		}
	}
	return false
}

func _exist(board [][]byte, word string, row int, col int, visited [][]bool) bool {
	if row < 0 || row >= len(board) || col < 0 || col >= len(board[row]) {
		return false
	}
	if visited[row][col] {
		return false
	}
	if len(word) == 1 && word[0] == board[row][col] {
		return true
	}
	if board[row][col] != word[0] {
		return false
	}
	visited[row][col] = true
	result := _exist(board, word[1:], row+1, col, visited) ||
		_exist(board, word[1:], row, col+1, visited) ||
		_exist(board, word[1:], row-1, col, visited) ||
		_exist(board, word[1:], row, col-1, visited)

	visited[row][col] = false
	return result
}
